package codeTopPractice;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

/**
 * @LeetCode 第 2 题
 *
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 * 这道算法本人写了两种解法，第一种常规的双for遍历，第二种双指针一次循环
 *
 * 结尾附leetcode最佳解法
 */

public class 无重复字符的最长子串长度 {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        String sc = scanner.next();
        System.out.println(lengthOfTheLongestSubStringDoublePoint(sc));
    }


    /**
     * 第一版
     * 本人基于最常规的思路写出双for循环遍历，时间复杂度O2
     * leetcode案例全部通过
     * 耗时 112ms， 内存消耗 72.7MB；
     */
    public static int lengthOfTheLongestSubStringDoubleForLoop(String s) {

        if (s.equals("") || s == null) {
            return 0;
        }

        char[] chars = s.toCharArray();
        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 0; i < chars.length; i++) {
            if (i == chars.length - 1) {
                list.add(1);
            }
            HashMap<Character, Integer> map = new HashMap<>();
            for (int j = i; j < chars.length; j++) {
                if (!map.containsKey(chars[j])) {
                    map.put(chars[j], j - i + 1);
                } else {
                    list.add(j - i);
                    break;
                }
                list.add(j - i);
            }

        }

        int max = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            max = max > list.get(i) ? max : list.get(i);
        }
        return max;
    }

    /**
     * 由于第一版的双for循环内存消耗大并且效率不高，改用双指针和一次循环重构代码，时间复杂度O1
     * leetCode 所有案例通过
     * 耗时 6ms，内存消耗41.3MB
     */
    public static int lengthOfTheLongestSubStringDoublePoint(String s) {

        int length = 0;

        if(s.length() == 0 || "".equals(s) || s == ""){
            return length;
        }
        int i = 0;
        int j = 0;
        ArrayList<Integer> list = new ArrayList<>();
        HashMap<Character, Integer> map = new HashMap<>();
        while (i < s.length()){

            if(map.containsKey(s.charAt(i))){
                if(map.get(s.charAt(i)) < j ){
                    map.remove(s.charAt(i));
                }
            }

            if(map.containsKey(s.charAt(i))){
                list.add(i - j);
                j = map.get(s.charAt(i))+1;
                map.put(s.charAt(i),i);
                i++;
            }else {
                map.put(s.charAt(i),i);
                i++;
            }
        }
        list.add(i-j);


        for (int k = 0; k < list.size() ; k++) {
            length = length > list.get(k) ? length : list.get(k);
        }

        return length;
    }

    /**
     * leetcode 最佳答案
     * 耗时 4ms，内存消耗41.3MB
     *
     * 作者：powcai
     * 链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/solution/hua-dong-chuang-kou-by-powcai/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

    public static int theBestMethod(String s){
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        int left = 0;
        for(int i = 0; i < s.length(); i ++){
            if(map.containsKey(s.charAt(i))){
                left = Math.max(left,map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-left+1);
        }
        return max;


    }
}